Vi kørte flere tests med de forskellige algoritmer, så vi kunne se hvordan de
klarede sig individuelt og sammenlignet med hinanden. Det vi præcist er
interesseret i er at undersøge forholdet mellem ventetiden for playback og tiden
for færdiggørelse af filen over flere sessioner. Her følger en beskrivelse af vores forsøg og de tilhørende resultater.

\subsection{Opsætning}

For at have mest mulig kontrol med forsøgene, udførte vi dem internt. Dvs. algoritmerne blev testet på seks maskiner, hvor hver algoritme blev kørt fem gange. En af maskinerne var en dedikeret tracker, som vi brugte i den torrent vi lavede. To andre maskiner var dedikeret seeders, dvs. de hentede ikke dele af filen, men kontaktede trackeren og ventede på forbindelser fra andre peers. Desuden da nogle algoritmer krævede en server, havde vi også en intern HTTP server kørende med filen. De tre andre maskiners opgave var at hente filen. De maskiner kørte samme algoritme og tilsluttede sig netværket på ca. samme tid (et mindre flash-crowd scenario). Når maskinerne blev færdige med at hente, blev filen slettet og forsøget startet igen. De tre maskiner var begrænset til en download hastighed på 4 Mbits/s og upload hastighed på 0.5 Mbits/s.

Til testen blev en fil på 169 megabyte brugt med en bitrate på 1911000 bits/sekund. Her antog vi at hele filen er ``spilbar'', og så borte fra mulige fil headers og andet meta-data i filen.

Da alle algoritmer er kompatible med BitTorrent protokollen udførte vi tilsidst tre mindre forsøg, hvor vi med hver algoritme tilsluttede os et rigtigt swarm. Til dette formål blev en mindre fil på 50 megabyte brugt, med høj antal seeders (ca. 25) og næsten ingen leechers.

\subsection{Resultater}

I vores kontrollerede tests ville vi se hvordan udviklingen var, hvis alle
klienterne brugte samme algoritme. BitTorrent er skabt til hurtig overførsel af store filer, det interessante er om et ``større'' antal af vores algoritmer ville kvæle filoverførelsen og resultere i at nogle klienter ikke kunne få den fuldstændige fil og hvis de fik den, hvor lang tid skulle de så vente playback, dvs. hvor stor var ventetiden på at kunne starte afspilningen af filen uden at den begyndte at buffer i midten af filen. Da vi kørte hver algoritme på tre maskiner per session, giver det os i alt 15 logfiler som udgangspunkt, dog havde vi problemer med udførelsen af nogle af algoritmerne på en computer, så dens logfil mangler i nogle sessioner.

\subsubsection{BASS}

BASS fungere ved at opdele filen i stykker (vinduer) som hver indeholder flere pieces. Pieces hentes fra serveren, hvis de ikke er muligt at nå at hente dem (udfra bitrate) fra andre peers. Et vindue hentes udelukkende fra serveren, når det først er startet, hvor de pieces som allerede er hentet hoppes over. Samtidigt med at resten af filen hentes i rækkefølge fra andre peers.

Umiddelbart er der den problemstillingen om systemet kunne risikere at gå ned, idet de mest efterspurgte pieces af filen er de første, kunne man risikere at de sidste stykker forsvinder fra systemet. Dog er serveren altid tilgengældig som backup, men hvilken betydning har det så for den overordnede ydeevne. 

\insertfigure{bass-comp.pdf}{BASS: Tiden for færdiggørelse af filen fordelt over sessionerne. Hvor ``comp'' 1,2,3 er de tre maskiners tider, ``average'' er sessionens gennemsnit og ``overall average'' er gennemsnittet over alle sessioner.}{fig:bass_comp}

Som man kan se ud fra fig.~\ref{fig:bass_comp} er tiden for færdiggørelse
forholdsvis konstant, den afviger ikke mere end 30 sekunder fra gennemsnittet,
og de tre maskiner følger hinanden nøje.

\insertfigure{bass-play.pdf}{BASS: Ventetiden på playback fordelt over sessioner.}{fig:bass_play}

Ventetiden på playback i fig.~\ref{fig:bass_play} er udregnet ud fra bitraten. Givet bitraten $R$ i pieces/sekund (som vi kan udregne ud fra biraten og piece størrelsen) og lad $\Delta t_{i}$ være tiden piece $i$ blev downloadet færdigt. Da vil vi gerne finde mindste $t$ som opfylder $\Delta t_{i} \leq t + \frac{i}{R}$ for alle pieces $i$. Og det er præcist det $t$ som er givet ved $max_{i} \lbrace \Delta t_{i} - \frac{i}{R} \rbrace$.

Udfra fig.~\ref{fig:bass_play} kan man se at tiderne variere noget mere, hvor
den værste variation forekommer i den sidste session, hvor variationen er fra
lidt over ti sekunder op til ca. 45 sekunder. Men gennemsnittet holder sig
mellem 30 og 35 sekunder. Variationen kan skyldes at det første vindue altid vil
blive hentet fra serveren, den hurtigste vil kunne udnytte serveren helt til at starte med, så når de andre kommer på vil serveren blive belastet og langsommere. Men efter et stykke tid vil den hurtigste kunne begynde at uploade til de andre, så færdiggørelses tiden bliver stortset ens.

\insertfigure{bass-arrival.pdf}{BASS: Ankomsttiderne for pieces. ``Average''
viser den gennemsnitlig anskomsttid (det der menes med ``average'' er linien
med tilpasset hældning i forhold til punkterne, startende i tiden nul) og
``playback'' svarer til playbackraten, hvis afspilning begyndte i tid
nul.}{fig:bass_arrival}

Hældningen på playback linien i fig.~\ref{fig:bass_arrival} er givet ud fra $R = \frac{R_{0}}{8 * pieceLength}$, hvor $R_{0}$ er bitraten i bits/sekund.

Dataen til grafen er taget fra den samme makine og dækker alle fem sessioner.
Som man kan se holder ankomsttiden sig nogenlunde konstant og altid over
playback, dette skyldes igen at der er en server som backup og at BASS foretrækker at hente fra serveren frem for andre peers.

\subsubsection{VodBT}

VodBT bruger internt to vinduer, i den første hentes pieces i den rækkefølge de optræder, i den anden hentes de i tilfældig rækkefølge (optimalt ville være at hente med rarest first, men det understøttes ikke af det underliggende framework). Når alle pieces i første vindue er hentet, hentes pieces i andet vindue, og disse vinduer flyttes efter et givet tidsinterval. Hvis efter det tidsinterval ikke alle pieces i det første vindue er hentet, hentes de fra serveren. I forhold til BASS prioriterer VodBT peers fremfor serveren.

For at undgå problemet med at systemet går ned pga. de sidste pieces mangler, bruger VodBT både server og random piece udvælgelse engang imellem.

\insertfigure{vodbt-comp.pdf}{VodBT: Tiden for færdiggørelse af filen fordelt over sessionerne.}{fig:vodbt_comp}

I fig.~\ref{fig:vodbt_comp} er der nogle variationer, men de sidste forsøg er konstante. I sammenligning med BASS tager det gennemsnitligt ca. 300 sekunder mere at downloade hele filen. Dette skyldes som nævnt at BASS prioritere serveren, og i vores forsøg har serveren en høj uploade hastighed. 

\insertfigure{vodbt-play.pdf}{VodBT: Ventetiden på playback fordelt over sessioner.}{fig:vodbt_play}

Som forventet er ventetiden på playback noget større (fig.~\ref{fig:vodbt_play}) end sammenlignet med BASS. De tre maskiner ser ud til at nogenlunde følge hinanden.

\insertfigure{vodbt-arrival.pdf}{VodBT: Ankomsttiderne for pieces.}{fig:vodbt_arrival}

Af fig.~\ref{fig:vodbt_arrival} kan man se at den gennemsnitlige anskomsttid holder sig lige over playback. Ankomsten af pieces følger et bestemt mønster, med punkter koncentreret i flere cirkler. Disse skyldes serveren, da den har en bedre forbindelse bliver disse pieces hentet hurtigere og da serveren går igang når vinduerne rykkes (samme tidsinterval hver gang), opstår disse udsving. Kigger man på anskomsttiden under BASS, så klare BASS sig lidt bedre. VodBT holder sig gennemsnitligt lige over playback og har større ventetid.\\[1em]

Umiddelbart kunne virke som BASS er bedre af de to algoritmer. BASS havde en stor fordel i vores forsøg nemlig at serveren havde stortset ubegrænset upload, og var under lille belastning. Under virkelig forhold ville sådan en server være under større belastning fra flere peers, og det kan være dyrt at have en server stående dedikeret kun til upload af filer. Derfor er det også en fordel, hvis algoritmerne i mindre grad afhang af serveren, da det også udgør en single point of failure i systemet. Vi kan også se at BASS hentede 18\% af dens pieces fra serveren mens VodBT klarede sig med 12\%. Under mere realistiske forhold vil begge disse tal være større. Dog klarede BASS sig en del bedre i de andre metrikker og med kun 6\% point forskel, det kan dog betyde noget med flere hundrede peers.

Begge algoritmer kan fungere hvis serveren skulle gå ned. Men da svare BASS bare til en greedy algoritme som henter pieces i rækkefølge fra peers, og i det tilfælde er der gode muligheder for at systemet kommer til at mangle nogle af de sidste pieces i filen. I modsætning anvender VodBT engang imellem random piece selection (som nævnt ville rarest first være bedre), til at forbedre ydeevnen af hele systemet.

\subsubsection{LiveBT}

LiveBT adskiller sig fra de to forrige algoritmer idet den ikke bruger en server. Istedet for anvendes flere subrutiner for at forbedre ydeevnen. Pieces hentes enten i rækkefølge eller hvorvidt de er efterspurgte i systemet. Der holdes konstant øje med hastigheden på de forskellige peers, og hvis et piece ikke kan nå (i forhold til playback) at blive hentet fra den peer som er er ansvarligt for den, bliver det piece tildelt til en hurtigere peer.

LiveBT arbejder med konceptet ``Most wanted peer block'' og ``Most wanted system block'', som hhv. er det piece med højest prioritet som peer'en mangler (det første piece i rækkefølgen som peer'en ikke har) og det piece med højest prioritet som flest peers ikke har. Enten henter en peer fra den en kategori eller den anden. På den måder prøver man at undgå en situation, hvor systemet kommer til at mangle nogle pieces eller at der opstår stor kø for at hente et piece.

\insertfigure{livebt-comp.pdf}{LiveBT: Tiden for færdiggørelse af filen fordelt over sessionerne.}{fig:livebt_comp}

Som forventet følger der af fig.~\ref{fig:livebt_comp} at det tager længere tid
at hente hele filen færdigt. Det man kan bemærke er dog at gennemsnitligt
forskellen mellem VodBT og LiveBT er ca. 150 sekunder, som er halvdelen af
forskellen mellem BASS og VodBT, og det er selvom VodBT har en fordel
med serveren.

\insertfigure{livebt-play.pdf}{LiveBT: Ventetiden på playback fordelt over sessioner.}{fig:livebt_play}

Ventetiden variere en del (fig.~\ref{fig:livebt_play}). I tre af sessionerne er
ventetiden for alle maskiner på samme niveau som BASS, mens de to andre
overstiger 500 sekunder. Det overordnede gennemsnit svare til øvregrænsen for VodBT ventetid, og er dobbelt så stor som dens gennemsnit. Dette mere kaotiske billede i forhold til de to andre algoritmer skyldes muligvis manglen på en server. Da LiveBT udelukkende støtter sig op ad den eksisterende BitTorrent protokol, er den underlagt dens regler om hvornår den bliver unchoket af andre peers, så den kan begynde at downloade.

\insertfigure{livebt-arrival.pdf}{LiveBT: Ankomsttiderne for pieces.}{fig:livebt_arrival}

Fig.~\ref{fig:livebt_arrival} viser igen et lidt mere varieret billede end ved
de to andre algoritmer. Gennemsnittet ligger også under playback i højere grad
end set før. Men det ses tydeligt at udviklingen følger en liniær udvikling.
Egetligt er det underligt at man ikke se en større effekt af udvælgelsen af pieces til hentning som ligger i kategorien ``Most wanted system blocks''. Dog kan man nogle steder se mindre afvigelser. Men det skyldes muligvis at pieces i den nævnte kategori hentes med 20\% sandsynlighed og at maskinen som dataen kommer fra var en hurtig downloader og lå foran de andre, i så fald vil den allerede have de mest efterspurgte som de to andre gerne vil have.\\[1em]

Det man kan se er at LiveBT klarer sig udemærket i forhold til de to andre
algoritmer selvom den ikke bruger en server. Dens tid for færdiggørelse af filen er højere, men er ikke alt for langt fra VodBT. Dog koster det i ventetiden på playback, hvor der sker et større hop. LiveBT har fordelen at den udelukkende bruger peers til at hente fra, hvilket betyder ingen single point of failure.

\subsection{Observationer}

For at være istand til at følge udviklingen, da vi testede algoritmerne, havde vi udviklet et piece progress bar. Den kunne fortælle os om et piece var anmodet, hentet fra en anden peer eller hentet fra serveren. Her var det nemt at se algoritmernes karakteristika. Til at starte med opførte algoritmerne sig nogenlunde ens, de prioriterede alle de første pieces som de ikke havde, senere kunne man sagtens se en forskel.

\begin{figure}[h!]
\begin{center}
	\includegraphics[width=\textwidth]{progress-bar-crop.png}
\end{center}
	\caption{\textit{Piece progress bar. Rød: piece er anmodet. Blå: piece hentet fra en anden peer. Grøn: piece hentet fra serveren.}}
	\label{fig:progress_bar}
\end{figure}

BASS starter altid ud med at hente det første vindue fra serveren mens andre
pieces hentes samtidigt fra peers i resten af filen, hvor de pieces med lav
nummer blev hentet først, hvis muligt. Når serveren blev færdig med et vindue gik den igang med den næste, hvor den hoppede over pieces som den allerede havde.

VodBT henter til at starte med pieces i det første fra vindue fra andre peers, og når den bliver færdig med vinduet går den i random rækkefølge igang med pieces i vindue to. Eller hvis den ikke blev færdig med første vindue i tide kunne man se hvordan de manglende pieces blev hentet fra serveren.

LiveBT startede ud som VodBT, men jo længere tid der gik kom de tre maskiner til forskellige steder i filen og man kunne se at LiveBT engang imellem hentede pieces længere fremme (svarende til at den henter ``Most wanted system block''). Sådan skiftede den mellem at hente pieces i rækkefølge og pieces som lå foran. 

\subsection{Testing ``In the wild''}

Vi afprøvede alle tre algoritmer ude i en rigtig swarm. Dette var et uformelt
forsøg, hvor vi bare observerede om de kunne overleve blandt rigtige peers. Vi gav BASS og VodBT adgang til en server med filen som blev delt. Alle algortimer var istand til at hente filen uden problemer og med ca. de tider vi havde fra vores mere kontrollerede forsøg. Dog brugte BASS og VodBT serveren mere til at hente pieces. Overordnet set skulle der ikke være problemer med at benytte algoritmerne under virkelige forhold.
